package hzk.codex2016.list;

public class LinkedList_mergeSort {

	/**
	 * https://leetcode.com/problems/sort-list/
	 * @param head
	 * @return
	 */
	public ListNode sortList(ListNode head) {
		if (head==null) return null;
		int len=0;
		for (ListNode p=head;p!=null;p=p.next) len++;
		
		return msort(head,len);
    }
	ListNode msort(ListNode head,int len){
		if (len==1) return head;
		int len1=len/2,len2=len-len1;
		ListNode h1=head,h2=head.next,h2pre=head;
		for (int k=len1-1;k>0;k--) {
			h2pre=h2;
			h2=h2.next;
		}
		 
		h2pre.next=null;	//split left and right
		h1=msort(h1,len1);
		h2=msort(h2,len2);
		
		return merge(h1,len1,h2,len2);
	}
	ListNode merge(ListNode head1,int len1,ListNode head2,int len2){
		ListNode tmpfh=new ListNode(0);	//temp fake head
		ListNode p,pre=tmpfh;
		while(len1>0 && len2>0){
			if(head1.val<head2.val){
				p=head1;
				head1=head1.next;
				len1--;
			}else{
				p=head2;
				head2=head2.next;
				len2--;
			}
			//append p to pre
			pre=pre.next=p;
		}
		if (len1>0) pre.next=head1;
		if (len2>0) pre.next=head2;
		return tmpfh.next;
	}
	
	public static void main(String[] args){
		LinkedList_mergeSort s=new LinkedList_mergeSort();
		System.out.println(s.sortList(Lists.sll()));
		System.out.println(s.sortList(Lists.sll(3)));
		System.out.println(s.sortList(Lists.sll(3,7)));
		System.out.println(s.sortList(Lists.sll(5,3)));
		System.out.println(s.sortList(Lists.sll(5,3,6)));
		System.out.println(s.sortList(Lists.sll(4,1,5,2)));
		System.out.println(s.sortList(Lists.sll(6,45,13,24,7,1,2,18,9,6,3,10)));
		
	}
}
